class Permute46:
    """
    46. 全排列
    给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

    示例 1：
    输入：nums = [1,2,3]
    输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
    示例 2：

    输入：nums = [0,1]
    输出：[[0,1],[1,0]]
    示例 3：

    输入：nums = [1]
    输出：[[1]]

    提示：

    1 <= nums.length <= 6
    -10 <= nums[i] <= 10
    nums 中的所有整数 互不相同
    """
    def permute(self, nums):
        res = []
        temp = []
        flg = [False * len(nums) for _ in range(len(nums))]
        self.back_per(nums, res, temp, flg, 0)
        return res

    def back_per(self, nums, res, temp, flg, index):
        if len(nums) == index:
            res.append([temp[0:]])

        for i in range(len(nums)):
            if flg[i]:
                continue
            temp.append(nums[i])
            flg[i] = True
            self.back_per(nums, res, temp, flg, index + 1)
            del temp[index]
            flg[i] = False
